package com.levi.linkedlist;

import java.util.Stack;

/**
 * @author shentong
 * @date 2021/8/22 21:41
 * @Description 单向链表的操作实现
 *
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        var hero1 = new HeroNode(4, "路飞", "海贼王");
        var hero2 = new HeroNode(1, "索隆", "剑豪");
        var hero3 = new HeroNode(3, "山治", "老色批");
        var hero4 = new HeroNode(2, "乔巴", "神医");
        var hero5 = new HeroNode(1, "乔巴", "神医");
        var heroNodeList = new HeroNodeList();
        //添加元素
    /*    heroNodeList.add(hero1);
        heroNodeList.add(hero2);
        heroNodeList.add(hero3);
        heroNodeList.add(hero4);*/

        heroNodeList.addByOrder(hero1);
        heroNodeList.addByOrder(hero2);
        heroNodeList.addByOrder(hero3);
        heroNodeList.addByOrder(hero4);
//        heroNodeList.addByOrder(hero5);
        //打印链表中的数据
        System.out.println("修改前的链表:-------");
        heroNodeList.list();
        heroNodeList.updateBode(5,"娜美","航海士");
        System.out.println("修改后的链表:-------");
        heroNodeList.list();
//        System.out.println("删除后的链表:------------");
//        heroNodeList.delteByNo(1);
//        heroNodeList.delteByNo(4);
//        heroNodeList.delteByNo(3);
//        heroNodeList.delteByNo(2);
//        heroNodeList.list();
        //获取单链表节点的个数
        System.out.printf("单链表的节点个数为:%d\n",heroNodeList.size());
        int k = 4;
        System.out.printf("单链表中倒数第%d个节点是:"+heroNodeList.getK(k)+"\n",k);

//        System.out.println("反转后的链表是:--------");
//        heroNodeList.reverse();
//        heroNodeList.list();
        System.out.println("逆序打印单链表");
        heroNodeList.reversePrint();
    }
}

class HeroNodeList{
    private final HeroNode head = new HeroNode(null,"","");
    /**
     * 往链表的最后添加元素(不按照编号的顺序)
     * @param node
     */
    public void add(HeroNode node) {
        //1.先找到链表的最后一个元素，即next为null的元素
        //2.head不能动，所以要用一个辅助节点,然后开始遍历找到next为null的节点位置
        var temp = head;
        while (temp.next != null) {
            //3.如果temp.next为null说明这时候tem是链表的最后一个元素，退出循环
            temp = temp.next;
        }
        //4.退出循环的时候temp是最后一个元素,就把最后一个元素的next指向要添加的元素
        temp.next = node;
    }

    /**
     * 按照英雄的编号有顺序的添加(有顺序的添加)
     * 如果要添加的节点的编号已经存在则抛出异常提示
     * @param node
     */
    public void addByOrder(HeroNode node) {
        //【解题思路】
        //1.头节点不能动，所以需要一个辅助节点temp，这个辅助节点必须选择新添加节点位置的前一个位置
        //2.找到位置的条件:temp.next节点大于要添加的节点  ,需要循环遍历来找到
        //3.赋值  node.next = temp.next        temp.next = node
        var temp = head;
        var flag = true;
        while (true) {
            //temp.next == null说明是最后一个节点了，不需要再遍历了
            if (temp.next == null) {
                break;
            //找到了节点要添加的位置了
            } else if (temp.next.no > node.no) {
                break;
            //已经有编号存在
            }else if (temp.next.no.equals(node.no)){
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            node.next = temp.next;
            temp.next = node;
        } else System.out.printf("要添加的英雄编号%d已经存在，不能重复添加\n",node.no);
    }

    /**
     * 修改链表节点的信息
     *  先需要一个辅助节点，然后遍历链表找到编号为no的节点，然后进行修改
     */
    public void updateBode(Integer no,String nickName,String name) {
        var temp = head;
        var flag = false;//用于判断有没有找到对应的node
        while (true) {
            //遍历到最后了
            if (temp.next == null) {
                break;
                //找到对应的节点了
            } else if (temp.next.no.equals(no)) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next.name = name;
            temp.next.nickName = nickName;
        }else System.out.printf("没有找到no为%d的节点\n",no);
    }

    /**
     * 根据编号删除节点
     * @param no
     */
    public void delteByNo(Integer no) {
        var temp = head;
        var flag = false;
        while (true){
            if (temp.next == null) {
                return;
                //因为是单链表，必须要找到待删除节点的前一个位置才行，所以这里是temp.next.no.equals(no)
            } else if (temp.next.no.equals(no)) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        }else System.out.printf("没有找到编号为%d的节点\n",no);
    }
    /**
     * 遍历链表
     */
    public void list(){
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        var temp = head;
        while (temp.next!= null){
            var node = temp.next;
            System.out.println(node);
            temp = temp.next;
        }
    }

    /**
     * 获取单链表的节点个数
     * @return int
     */
    public int size() {
        var temp = head;
        var sum = 0;
        while (temp.next != null) {
            sum++;
            temp = temp.next;
        }
        return sum;
    }

    /**
     *
     * 返回单链表中倒数第k个节点(新浪面试题)
     * 1.先算出节点的总个数size
     * 2.遍历全部，遍历到第(size - k),就是要得到的节点
     * @param k
     * @return
     */
    public HeroNode getK(Integer k) {
        //让tem指向第一个有效的节点
        var temp = head.next;
        int size = size();//单向链表的长度
        if (k<=0 || k>size) {
            return null;
        }
        for (int i = 0; i <size-k; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     *
     * 反转单链表(腾讯面试题)
     * 1.创建一个新的链表reverse
     * 2.逐个遍历原来的链表，把遍历出来的节点放在新节点的头部
     * 3.把原来节点的头部的下一个节点指向新节点头部的下一个节点
     */
    public void reverse() {

        //如果链表为空或者只有一个元素 直接return
        if (head.next == null || head.next.next == null) {
            return;
        }
        var current = head.next;//辅助节点
        var reverseHead = new HeroNode(0, "", "");//新的单链表的头节点
        HeroNode next = null;
        while (current != null) {
            next = current.next;//先获取current的next节点，以后要用
            current.next = reverseHead.next;//把current的下一个节点挂在新链表的最前面
            reverseHead.next = current;//把current挂在current.next之后
            current = next;//让current后移
        }
        head.next = reverseHead.next;
    }

    /**
     * 逆序打印单链表
     * 1.把链表的节点放进Stack中，然后pop取出来
     */
    public void reversePrint() {
        Stack<HeroNode> stack = new Stack<>();
        if (head.next == null) {
            return;
        }
        var temp = head.next;
        //循环遍历节点并且入栈
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        //出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}


 class HeroNode{
     public Integer no;
     public String name;
     public String nickName;
     public HeroNode next;

     public HeroNode(Integer no, String name, String nickName) {
         this.no = no;
         this.name = name;
         this.nickName = nickName;
     }

     @Override
     public String toString() {
         return "HeroNode{" +
                 "no=" + no +
                 ", name='" + name + '\'' +
                 ", nickName='" + nickName + '\'' +
                 '}';
     }
 }
